import (
	"math/rand"
	"time"
)

/*
 * @lc app=leetcode.cn id=1206 lang=golang
 *
 * [1206] 设计跳表
 */

// @lc code=start

const MaxLevel = 32
const p = 0.5

type Skiplist struct {
	Head  *Node
	Level int
}

type Node struct {
	Key     int
	Forward []*Node
}

func Constructor() Skiplist {
	return Skiplist{Head: &Node{Forward: make([]*Node, MaxLevel)}, Level: 1}
}

func randomLevel() int {
	level := 1
	rand.Seed(time.Now().UnixNano())
	for rand.Float64() < p && level < MaxLevel {
		level++
	}
	return level
}

func (this *Skiplist) Search(target int) bool {
	x := this.Head
	for i := this.Level - 1; i >= 0; i-- {
		for x.Forward[i] != nil && x.Forward[i].Key < target {
			x = x.Forward[i]
		}
	}

	x = x.Forward[0]
	if x != nil && x.Key == target {
		return true
	} else {
		return false
	}
}

func (this *Skiplist) Add(num int) {
	x := this.Head
	update := make([]*Node, MaxLevel)
	for i := this.Level - 1; i >= 0; i-- {
		for x.Forward[i] != nil && x.Forward[i].Key <= num {
			x = x.Forward[i]
		}
		update[i] = x
	}

	level := randomLevel()
	node := &Node{Forward: make([]*Node, level), Key: num}
	if level > this.Level {
		for i := this.Level; i < level; i++ {
			update[i] = this.Head
		}
		this.Level = level
	}

	for i := level - 1; i >= 0; i-- {
		node.Forward[i] = update[i].Forward[i]
		update[i].Forward[i] = node
	}
}

func (this *Skiplist) Erase(num int) bool {
	x := this.Head
	flag := false
	for i := this.Level - 1; i >= 0; i-- {
		for x.Forward[i] != nil {
			if x.Forward[i].Key == num {
				tmp := x.Forward[i]
				x.Forward[i] = tmp.Forward[i]
				tmp.Forward[i] = nil
				flag = true
				break
			} else if x.Forward[i].Key < num {
				x = x.Forward[i]
			} else {
				break
			}
		}
	}
	return flag
}

/**
 * Your Skiplist object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Search(target);
 * obj.Add(num);
 * param_3 := obj.Erase(num);
 */
// @lc code=end

